package kyssion.leetcode.num51_100;

import java.util.Arrays;

public class code88_合并两个有序数组 {
    public static void main(String[] args) {
        int[] num1 = new int[]{
                1,2,4,5,6,0
        };

        int[] num2 = new int[]{
                3
        };
        new code88_合并两个有序数组().merge(num1, 5, num2, 1);
        System.out.println();
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        mergeI(nums1, 0, m, nums2, 0, n);
    }

    private void mergeI(int[] nums1, int s1, int m, int[] nums2, int s2, int n) {
        if (m == 0 || n == 0 || nums1.length - m < n - s2) {
            return;
        }
        int i = s1;
        int j = s2;
        int index = m;
        while (i < m && j < n) {
            exchange(nums1, i, index);
            index++;
            if (nums1[m] >= nums2[j]) {
                nums1[i] = nums2[j];
                j++;
            } else {
                nums1[i] = nums1[m];
                for (int a = m + 1; a < index; a++) {
                    nums1[a - 1] = nums1[a];
                }
                index--;
            }
            i++;
        }
        if (j == n) {
            //这里缺少一个校验代码 如果 m ! = index 的时候将会出现问题有部分数据没有插入的情况
            return;
        } else {
            if (m == index) {
                while (j < n) {
                    nums1[m] = nums2[j];
                    j++;
                    m++;
                }
            } else {
                mergeI(nums1, m, index, nums2, j, n);
            }
        }
    }


    public void exchange(int[] arr, int s, int n) {
        int a = arr[s];
        arr[s] = arr[n];
        arr[n] = a;
    }

    /**
     * 从后向前其实就不需要特殊处理了
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int p = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }

        while (n >= 0) {
            nums1[p--] = nums2[n--];
        }
    }
}
